home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / me_cd.zip / GOMOKU.MUT < prev    next >
Lisp/Scheme  |  1988-09-26  |  44KB  |  1,343 lines
  1. ;;   Once installed and compiled, the program is invoked with 'M-x gomoku'
  2. ;; and 'C-h m' (the well-known describe-mode) will list all key bindings
  3. ;; provided to the player.  Have fun.
  4.  
  5. ;;; Gomoku game between you and GNU Emacs.  Last modified on 13 Sep 1988
  6. ;;; Converted to Mutt 9/88 C Durland
  7. ;;;
  8. ;;; Written by Ph. Schnoebelen (phs@lifia.imag.fr), 1987, 1988
  9. ;;; with precious advices from J.-F. Rit.
  10. ;;; This has been tested with GNU Emacs 18.50.
  11. ;;;
  12. ;;; This software is distributed 'as is', without warranties of any
  13. ;;; kind, but all comments, suggestions and bug reports are welcome.
  14.  
  15.  
  16. ;; RULES:
  17. ;;
  18. ;; Gomoku is a game played between two players on a rectangular board.    Each
  19. ;; player, in turn, marks a free square of its choice. The winner is the first
  20. ;; one to mark five contiguous squares in any direction (horizontally,
  21. ;; vertically or diagonally).
  22. ;;
  23. ;; I have been told that, in "The TRUE Gomoku", some restrictions are made
  24. ;; about the squares where one may play, or else there is a known forced win
  25. ;; for the first player. This program has no such restriction, but it does not
  26. ;; know about the forced win, nor do I.     Furthermore, you probably do not know
  27. ;; it yourself :-).
  28.  
  29.  
  30. ;; HOW TO INSTALL:
  31. ;;
  32. ;; There is nothing specific w.r.t. installation: just put this file in the
  33. ;; lisp directory and add an autoload for command gomoku in site-init.el. If
  34. ;; you don't want to rebuild Emacs, then every single user interested in
  35. ;; Gomoku will have to put the autoload command in its .emacs file.  Another
  36. ;; possibility is to define in your .emacs some command using (require
  37. ;; 'gomoku).
  38. ;;
  39. ;; The most important thing is to BYTE-COMPILE gomoku.el because it is
  40. ;; important that the code be as fast as possible.
  41. ;;
  42. ;; There are two main places where you may want to customize the program: key
  43. ;; bindings and board display. These features are commented in the code. Go
  44. ;; and see.
  45.  
  46.  
  47. ;; HOW TO USE:
  48. ;;
  49. ;; Once this file has been installed, the command "M-x gomoku" will display a
  50. ;; board, the size of which depends on the size of the current window. The
  51. ;; size of the board is easily modified by giving numeric arguments to the
  52. ;; gomoku command and/or by customizing the displaying parameters.
  53. ;;
  54. ;; Emacs plays when it is its turn. When it is your turn, just put the cursor
  55. ;; on the square where you want to play and hit RET, or X, or whatever key you
  56. ;; bind to the command gomoku-human-plays. When it is your turn, Emacs is
  57. ;; idle: you may switch buffers, read your mail, ... Just come back to the
  58. ;; *Gomoku* buffer and resume play.
  59.  
  60.  
  61. ;; ALGORITHM:
  62. ;;
  63. ;; The algorithm is briefly described in section "THE SCORE TABLE". Some
  64. ;; parameters may be modified if you want to change the style exhibited by the
  65. ;; program.
  66.  
  67.  
  68. (include me.h)
  69. (include mod.mut)
  70. (include random.mut)
  71. (include max.mut)
  72. (include min.mut)
  73.  
  74. ;;;
  75. ;;; GOMOKU MODE AND KEYMAP.
  76. ;;;
  77.  
  78. (include nomunge.mut)
  79.  
  80. (defun create-gomoku-mode-map
  81. {
  82.   (buffer-nomunge)
  83.  
  84.   ;; Key bindings for cursor motion. Arrow keys are just "function"
  85.   ;; keys, see below.
  86.   (bind-local-key "gomoku-move-nw"    "y")        ; Y
  87.   (bind-local-key "gomoku-move-ne"    "u")        ; U
  88.   (bind-local-key "gomoku-move-sw"    "b")        ; B
  89.   (bind-local-key "gomoku-move-se"    "n")        ; N
  90.   (bind-local-key "gomoku-move-left"    "h")        ; H
  91.   (bind-local-key "gomoku-move-right"    "l")        ; L
  92.   (bind-local-key "gomoku-move-down"    "j")        ; J
  93.   (bind-local-key "gomoku-move-up"    "k")        ; K
  94.   (bind-local-key "gomoku-move-down"    "C-n")        ; C-N
  95.   (bind-local-key "gomoku-move-down"    "F-D")        ; down arrow
  96.   (bind-local-key "gomoku-move-up"    "C-p")        ; C-P
  97.   (bind-local-key "gomoku-move-up"    "F-C")        ; up arrow
  98.   (bind-local-key "gomoku-move-right"    "C-f")        ; C-F
  99.   (bind-local-key "gomoku-move-right"    "F-E")        ; right arrow
  100.   (bind-local-key "gomoku-move-left"    "C-b")        ; C-B
  101.   (bind-local-key "gomoku-move-left"    "F-F")        ; left arrow
  102.  
  103.   ;; Key bindings for entering Human moves.
  104.   (bind-local-key  "gomoku-human-plays"        "X")    ; X
  105.   (bind-local-key  "gomoku-human-plays"        "x")    ; x
  106.   (bind-local-key  "gomoku-human-plays"        "C-m")    ; RET
  107. ; (bind-local-key  "gomoku-human-plays"        "C-Xp")    ; C-C P
  108.   (bind-local-key  "gomoku-human-resigns"    "C-Xr")    ; C-C R
  109.   (bind-local-key  "gomoku-emacs-plays"        "C-Xe")    ; C-C E
  110. ; (bind-local-key  "gomoku-human-takes-back"    "C-cb")    ; C-C B
  111. })
  112.  
  113.  
  114. ;;    Major mode for playing Gomoku against Emacs.  You and Emacs play in
  115. ;; turn by marking a free square.  You mark it with X and Emacs marks it
  116. ;; with O.  The winner is the first to get five contiguous marks
  117. ;; horizontally, vertically or in diagonal.  You play by moving the cursor
  118. ;; over the square you choose and hitting RET, x, ..  or whatever has been
  119. ;; set locally.
  120.  
  121. ;; Other useful commands:
  122. ;;   C-c r Indicate that you resign.
  123. ;;   C-c t Take back your last move.
  124. ;;   C-c e Ask for Emacs to play (thus passing).
  125.  
  126. (defun gomoku-mode
  127. {
  128. ;  (setq major-mode 'gomoku-mode    mode-name "Gomoku")
  129.   (gomoku-display-statistics)
  130.   (create-gomoku-mode-map)
  131. })
  132.  
  133. ;;;
  134. ;;; THE BOARD.
  135. ;;;
  136.  
  137. ;;   The board is a rectangular grid.  We code empty squares with 0, X's
  138. ;; with 1 and O's with 6.  The rectangle is recorded in a one dimensional
  139. ;; vector containing padding squares (coded with -1).  These squares allow
  140. ;; us to detect when we are trying to move out of the board.  We denote a
  141. ;; square by its (X,Y) coords, or by the INDEX corresponding to them in the
  142. ;; vector.  The leftmost topmost square has coords (1,1) and index
  143. ;; gomoku-board-width + 2.  Similarly, vectors between squares may be given
  144. ;; by two DX, DY coords or by one DEPL (the difference between indexes).
  145.  
  146. (const gomoku-max-vector-length 4000)
  147.  
  148.   ;; Number of columns on the Gomoku board.
  149. (int gomoku-board-width)
  150.  
  151.   ;; Number of lines on the Gomoku board.
  152. (int gomoku-board-height)
  153.  
  154.   ;; Vector recording the actual state of the Gomoku board.
  155. (array int gomoku-board gomoku-max-vector-length)
  156.  
  157.   ;; Length of gomoku-board vector.
  158. (int gomoku-vector-length)
  159.  
  160.   ;; After how many moves will Emacs offer a draw ?
  161.   ;; This is usually set to 70% of the number of squares.
  162. (int gomoku-draw-limit)
  163.  
  164.   ;; Translate X, Y cartesian coords into the corresponding board index.
  165. (defun gomoku-xy-to-index (int x y) { (+ (* y gomoku-board-width) x y) })
  166.  
  167.   ;; Return corresponding x-coord of board INDEX.
  168. (defun gomoku-index-to-x (int index) { (mod index (+ 1 gomoku-board-width)) })
  169.  
  170.   ;; Return corresponding y-coord of board INDEX.
  171. (defun gomoku-index-to-y (int index) { (/ index (+ 1 gomoku-board-width)) })
  172.  
  173.   ;; Create the gomoku-board vector and fill it with initial values.
  174. (defun gomoku-init-board
  175. {
  176.   (int i ii)
  177.  
  178. ;(setq gomoku-board (make-vector gomoku-vector-length 0))
  179.     ;; Every square is 0 (i.e. empty) except padding squares:
  180.  
  181.   (i gomoku-vector-length) (while (!= 0 (-= i 1)) (gomoku-board i 0))
  182.  
  183.   (i 0) (ii (- gomoku-vector-length 1))
  184.   (while (<= i gomoku-board-width)    ; The squares in [0..width] and in
  185.   {
  186.     (gomoku-board i  -1)        ;    [length - width - 1..length - 1]
  187.     (gomoku-board ii -1)        ;    are padding squares.
  188.     (+= i 1)(-= ii 1)
  189.   })
  190.  
  191.   (i 0)
  192.   (while (< i gomoku-vector-length)
  193.   {
  194.     (gomoku-board i -1)        ; and also all k*(width+1)
  195.     (+= i gomoku-board-width 1)
  196.   })
  197. })
  198.  
  199. ;;;
  200. ;;; THE SCORE TABLE.
  201. ;;;
  202.  
  203. ;; Every (free) square has a score associated to it, recorded in the
  204. ;; GOMOKU-SCORE-TABLE vector. The program always plays in the square having
  205. ;; the highest score.
  206.  
  207.   ;; Vector recording the actual score of the free squares.
  208. (array INT gomoku-score-table gomoku-max-vector-length)
  209.  
  210.  
  211. ;; The key point about the algorithm is that, rather than considering
  212. ;; the board as just a set of squares, we prefer to see it as a "space" of
  213. ;; internested 5-tuples of contiguous squares (called qtuples).
  214. ;;
  215. ;; The aim of the program is to fill one qtuple with its O's while preventing
  216. ;; you from filling another one with your X's. To that effect, it computes a
  217. ;; score for every qtuple, with better qtuples having better scores. Of
  218. ;; course, the score of a qtuple (taken in isolation) is just determin